#define DEBUG
#include <cstdio>

using namespace std;

bool check(int a, int b) {
  for (int i=0; i<4; i++) {
    if (((a>>i)&1)==0 && ((b>>i)&1)==0) {
      i++;
      if (i>=4 || ((a>>i)&1)!=0 || ((b>>i)&1)!=0) {
	return false;
      }
    }
    if (((a>>i)&1)==1 && ((b>>i)&1)!=0) {
      return false;
    }
  }
  return true;
}

void initMat(long long matrix[16][16]) {
  for (int i=0; i<16; i++) {
    for (int j=0; j<16; j++) {
      if (check(i, j)) {
	matrix[i][j]=1;
      }
    }
  }
}

void initOne(long long one[16][16]) {
  for (int i=0; i<16; i++) {
    one[i][i]=1;
  }
}

void calc(long long a[][16], long long b[][16], long long c[][16], int n, int m) {
  for (int i=0; i<n; i++) {
    for (int j=0; j<16; j++) {
      c[i][j]=0;
      for (int k=0; k<16; k++) {
	c[i][j] = (c[i][j]+a[i][k]*b[k][j]%m)%m;
      }
    }
  }
}

void copy(long long a[][16], long long b[][16]) {
  for (int i=0; i<16; i++) {
    for (int j=0; j<16; j++) {
      b[i][j]=a[i][j];
    }
  }
}

void qpower(long long a[16][16], long long one[16][16], int n, int m) {
  static long long ret[2][16][16], s[2][16][16];
  copy(a, ret[0]);
  copy(one, s[0]);
  int ir=0, is=0;
  for (; n>1; n/=2) {
    if (n%2) {
      is++;
      calc(s[(is-1)%2], ret[ir%2], s[is%2], 16, m);
    }
    ir++;
    calc(ret[(ir-1)%2], ret[(ir-1)%2], ret[ir%2], 16, m);
  }
  calc(ret[ir%2], s[is%2], a, 16, m);
}

int main() {
#ifdef DEBUG
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif

  static long long mat[16][16], temp[16][16], ans[1][16], ini[1][16]={{1}}, one[16][16];
  initMat(mat);
  initOne(one);
  int n, m;
  for (scanf("%d %d", &n, &m); n && m; scanf("%d %d", &n, &m)) {
    copy(mat, temp);
    qpower(temp, one, n, m);
    calc(ini, temp, ans, 1, m);
    printf("%lld\n", ans[0][0]);
  }

  fclose(stdin);
  fclose(stdout);
}
